package com.dys.datastructuresandalgorithm.selectsort;

/**
 * @className: com.dys.datastructuresandalgorithm.selectsort.SelectSort
 * @description: 选择排序
 * @author: pine cone
 * @version: v1.0.0
 * @createTime: 2024/05/27 下午8:48
 */
public class SelectSort {

    /**
     * 交换方法：交换一个整型数组中指定下标的两个元素。
     *
     * @param array  需要进行元素交换的整形数组
     * @param first  需要交换的第一个元素的下标。
     * @param second 需要交换的第二个元素的下标。
     */
    public static void swap(int[] array, int first, int second) {
        // 用临时变量存储array数组中第second个元素的值
        int temp = array[second];

        // 将array数组中第second个元素的值更新为第first个元素的值
        array[second] = array[first];

        // 将array数组中第first个元素的值更新为temp变量的值。
        array[first] = temp;
    }

    /**
     * 打印方法：打印整型数组元素
     *
     * @param array 等待打印的整型数组
     */
    public static void printArray(int[] array) {
        for (int j : array) {
            System.out.print(j + " ");
        }
        System.out.println();
    }

    /**
     * 选择排序：对传入的整型数组进行排序-->从小到大
     *
     * @param arr 等待传递的整型数组
     */
    public static void selectSort(int[] arr) {
        // 考虑边界情况: 若只有一个元素or没有元素,则不进行排序
        if (arr == null || arr.length < 2) {
            return;
        }

        // 获取数组的长度
        int n = arr.length;
        // 定义外部循环，控制选择的轮数，一共n-1轮: 0~n-1(选一个最小值,放到索引0的位置) | 1~n-1 | 2~n-1 | 3~n-1 ...| i~n-1
        for (int i = 0; i < n; i++) {
            // 默认第一个索引的元素为最小值
            int minValueIndex = i;
            // 内部循环进行比较,从第二个索引位置开始遍历
            for (int j = i + 1; j < n; j++) {
                minValueIndex = arr[j] < arr[minValueIndex] ? j : minValueIndex;
            }
            swap(arr, i, minValueIndex);
        }
    }

    public static void main(String[] args) {
        int[] exampleArray = {66, 33, 22, 11, 22, 44, 99};
        System.out.println("********未经过选择排序前的元素******");
        printArray(exampleArray);
        // 执行排序
        selectSort(exampleArray);
        System.out.println("********经过选择排序后的元素******");
        printArray(exampleArray);
    }

    /**
     * 选择排序：对传入的整型数组进行排序
     *
     * @param arr 等待传递的整型数组
     */
    public static void selectionSort(int[] arr) {
        // 获取到数组的长度
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            // 找到从i到n-1中最小元素的索引
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            // 将找到的最小元素与i位置的元素交换
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }

    public static void main2(String[] args) {
        int[] exampleArray = {66, 33, 22, 11, 22, 44, 99};
        System.out.println("********未经过选择排序前的元素******");
        for (int value : exampleArray) {
            System.out.print(value + " ");
        }
        System.out.println();
        // 进行排序
        selectionSort(exampleArray);
        System.out.println("********经过选择排序后的元素******");
        for (int value : exampleArray) {
            System.out.print(value + " ");
        }
    }

    /**
     * 选择排序练习
     * @param arr
     */
    public static void selectSort2(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        // 获取数组的长度
        int N = arr.length;
        // 0 ~ N-1 中选一个最小值,放到索引0的位置
        // 1 ~ N-1 中选一个最小值,放到索引1的位置
        // 2 ~ N-1 中选一个最小值,放到索引2的位置
        // 3 ~ N-1 中选一个最小值,放到索引3的位置
        // N-1 ~ N-1 中选一个最小值,放到索引N-1的位置
        for (int i = 0; i < N; i++) { // i掌管左侧的范围
            // i ~ N-1 ->
            // 0 ~ N-1
            // 1 ~ N-1
            // 2 ~ N-1
            // i ~ N-1
            int minIndex = i;// 如果仅仅看过i位置的数,i位置本身就是最小值所在的数
            // 选出最小值
            for (int j = i + 1; j < N; j++) {// i往后所有的位置,都检查一遍
                // 最小值位置是否更新?跟之前发现最小值的位置进行比较
                // arr[j]比之前找到的最小值位置的值还要小，就认为j是最小值所在的位置，否则，就维持不变
                minIndex = arr[j] < arr[minIndex] ? j : minIndex;
            }
            swap2(arr, i, minIndex);
        }
    }

    public static void swap2(int[] arr, int i, int j) {
        // 用一个临时变量做交换
        int temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }

    public static void selectSort3(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        int N = arr.length;
        for (int i = 0; i < N; i++) {
            int minIndex = i;
            for (int j = i + 1; j < N; j++) {
                minIndex = arr[j] < arr[minIndex] ? j : minIndex;
            }
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }


}
